package vip.meeet.algorithm.arr;


public class Num88 {

    public static void main(String[] args) {
        int[] a = {1,1,-10,1,1,1,1};
        System.out.println(maxSubArray(a));
    }

    public void merge(int[] nums1, int m, int[] nums2, int n) {


    }

    public static int maxSubArray(int[] nums) {
        int max = nums[0];
        for(int i=1;i<nums.length;i++){// 找到最大值
            if(max < nums[i]){
                max = nums[i];
            }
        }
        int sum = 0;
        for(int i=0;i<nums.length;i++){
            if(sum == 0 && nums[i] <= 0){// sum == 0时，负数没有增益，跳过
                continue;
            }
            sum += nums[i]; // sum值可能波动，但只要小于0，就说明已经这个子序列结束了
            max = max > sum ? max : sum;// 更新max
            if(sum < 0){
                sum = 0;
            }
        }
        return max;
    }

}
